package Hot100.leetcode.editor.cn.code.矩阵;

import java.util.HashSet;
import java.util.Set;

//Java：矩阵置零
public class SetMatrixZeroes{
    public static void main(String[] args) {
        Solution solution = new SetMatrixZeroes().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

            public void setZeroes(int[][] matrix) {
                //1. 第一种办法使用两个集合分别来记录那些行那些列有0，第二遍再置为0
                Set<Integer> row_zero = new HashSet<>();
                Set<Integer> clo_zero = new HashSet<>();

                int row = matrix.length;
                int col = matrix[0].length;

                for (int i = 0; i < row; i++) {
                    for (int j = 0; j < col; j++) {
                        if(matrix[i][j] == 0){
                            row_zero.add(i);
                            clo_zero.add(j);
                        }
                    }
                }
                for (int i = 0; i < row; i++) {
                    for (int j = 0; j < col; j++) {
                        if(row_zero.contains(i) || clo_zero.contains(j)){
                            matrix[i][j] = 0;
                        }
                    }
                }

                //2. 用matrix第一行和第一列记录该行该列是否有0,作为标志位 这个作为第二部分置为0
                //但是对于第一行,和第一列要设置一个标志位,为了防止自己这一行(一列)也有0的情况 第一部分置为0
                /*int row = matrix.length;
                int col = matrix[0].length;
                boolean row0_flag = false;
                boolean col0_flag = false;
                // 检查第一行是否有0元素
                for (int j = 0; j < col; j++) {
                    if (matrix[0][j] == 0) {
                        row0_flag = true;
                        break;
                    }
                }
                // 检查第一列是否有0元素
                for (int i = 0; i < row; i++) {
                    if (matrix[i][0] == 0) {
                        col0_flag = true;
                        break;
                    }
                }
                // 遍历除第一行第一列以外的所有元素，如果发现0
                //就将该元素对应的第一行和第一列位置置为0，作为标记
                for (int i = 1; i < row; i++) {
                    for (int j = 1; j < col; j++) {
                        if (matrix[i][j] == 0) {
                            matrix[i][0] = matrix[0][j] = 0;
                        }
                    }
                }
                // 第二部分置为0   根据第一行和第一列的标记将对应行列置为0
                for (int i = 1; i < row; i++) {
                    for (int j = 1; j < col; j++) {
                        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                            matrix[i][j] = 0;
                        }
                    }
                }

                // 如果原来第一行有0，则将第一行全部置为0
                if (row0_flag) {
                    for (int j = 0; j < col; j++) {
                        matrix[0][j] = 0;
                    }
                }
                // 如果原来第一列有0，则将第一列全部置为0
                if (col0_flag) {
                    for (int i = 0; i < row; i++) {
                        matrix[i][0] = 0;
                    }
                }
            }*/
            }


}
//leetcode submit region end(Prohibit modification and deletion)

}